package leetcode;


/**
 * 24.两两交换链表中的节点
 * <p>
 * 给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
 * <p>
 * 你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
 * <p>
 *  
 * <p>
 * 示例:
 * <p>
 * 给定 1->2->3->4, 你应该返回 2->1->4->3.
 *
 * @author: cuihao
 * @create: 2020-07-02 01:42
 **/
public class SwapPairs {

    /**
     * 递归。推荐
     *
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }

        return recursion(head);
    }

    public ListNode recursion(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = head.next;
        head.next = recursion(newHead.next);
        newHead.next = head;
        head = newHead;
        return head;
    }

    /**
     * 遍历
     *
     * @param head
     * @return
     */
    public ListNode swapPairs1(ListNode head) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        ListNode prev = dummyHead;
        // 只有当prev指向的结点之后有两个结点时才需要交换
        while (prev.next != null && prev.next.next != null) {
            ListNode node1 = prev.next;
            ListNode node2 = node1.next;
            ListNode subHead = node2.next;

            node2.next = node1;
            node1.next = subHead;
            prev.next = node2;

            // prev指向交换后的结点的第二个结点，
            // 即未交换结点的前一个结点
            prev = node1;
        }
        return dummyHead.next;
    }


    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}
